package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.list.singly.ListNode;
import leetcode.editor.cn.util.list.singly.ListUtil;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author qidi
 * @date 2022-01-17 13:04:46
 */
class Q0143_ReorderList {

    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public void reorderList(ListNode head) {
            if (head.next == null || head.next.next == null) return;

            ListNode slow = head;
            ListNode fast = head;

            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
                if (fast.next == null) break;
                fast = fast.next;
            }

            Deque<ListNode> stack = new ArrayDeque<>();
            while (slow != null) {
                stack.push(slow);
                slow = slow.next;
            }

            ListNode cur = head;
            while (!stack.isEmpty()) {
                ListNode node = stack.poll();
                if (node == cur) break;
                ListNode nn = cur.next;
                cur.next = node;
                node.next = nn;
                cur = nn;
            }
            cur.next = null;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new Q0143_ReorderList().new Solution();
        ListUtil util = ListUtil.getInstance();
        ListNode head = util.generateFromArray(1, 2, 3, 4);
        solution.reorderList(head);
        System.out.println(head);
        head = util.generateFromArray(1, 2, 3, 4, 5);
        solution.reorderList(head);
        System.out.println(head);
        head = util.generateFromArray(1, 2);
        solution.reorderList(head);
        System.out.println(head);
    }
}